home *** CD-ROM | disk | FTP | other *** search
/ Games of Daze / Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso / x2ftp / msdos / docs / winer / chap8-5.bas < prev    next >
Encoding:
BASIC Source File  |  1992-05-13  |  1.2 KB  |  49 lines
  1. '*********** CHAP8-5.BAS - indexed Binary search routine
  2.  
  3. 'Copyright (c) 1992 Ethan Winer
  4.  
  5. DEFINT A-Z
  6. DECLARE FUNCTION BinaryISearch% (Array$(), Index(), Find$)
  7.  
  8. CLS
  9. PRINT "Creating test data..."
  10.  
  11. REDIM Array$(1 TO 1000)         'create a "sorted" array
  12. REDIM Index(1 TO 1000)
  13. FOR X = 1 TO 1000
  14.   Array$(X) = "String " + RIGHT$("000" + LTRIM$(STR$(1000 - X)), 4)
  15.   Index(X) = 1000 - X
  16. NEXT
  17.  
  18. PRINT "Searching array..."
  19.  
  20. FoundAt = BinaryISearch%(Array$(), Index(), "String 0999")
  21. IF FoundAt >= 0 THEN
  22.   PRINT "Found at element"; FoundAt
  23. ELSE
  24.   PRINT "Not found"
  25. END IF
  26.  
  27. FUNCTION BinaryISearch% (Array$(), Index(), Find$) STATIC
  28.  
  29. BinaryISearch% = -1             'assume not found
  30. Min = LBOUND(Array$)            'start at first element
  31. Max = UBOUND(Array$)            'consider through last
  32.  
  33. DO
  34.   Try = (Max + Min) \ 2         'start testing in middle
  35.  
  36.   IF Array$(Index(Try)) = Find$ THEN    'found it!
  37.     BinaryISearch% = Try        'return matching element
  38.     EXIT DO                     'all done
  39.   END IF
  40.  
  41.   IF Array$(Index(Try)) > Find$ THEN    'too high, cut
  42.     Max = Try - 1
  43.   ELSE
  44.     Min = Try + 1               'too low, cut other way
  45.   END IF
  46. LOOP WHILE Max >= Min
  47.  
  48. END FUNCTION
  49.